import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/29 8:33
 * @description 贪心 + 入度
 */
public class Solution {
    public static void main(String[] args) {

    }
    public long maximumImportance(int n, int[][] roads) {
        int[] cnt = new int[n];
        // 计算每个节点的入度
        for (int[] r: roads) {
            cnt[r[0]]++;
            cnt[r[1]]++;
        }
        Arrays.sort(cnt);
        long ans = 0;
        // 逆序遍历
        for(int i = n-1; i >= 0; i--) {
            ans += (long) cnt[i] * n;
            n--;
        }
        return ans;
    }
}
